15. 三数之和

为保证权益，题目请参考 15. 三数之和(From LeetCode).

解决方案1

CPP

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;

        if (nums.size() < 3)
            return res;

        int left = 0;
        int right;
        int middle = 1;
        while (left < nums.size() - 2)
        {
            middle = left + 1;
            right = nums.size() - 1;

            while (middle < right)
            {
                if (nums[left] + nums[middle] + nums[right] == 0)
                {
                    vector<int> res_tmp;
                    res_tmp.push_back(nums[left]);
                    res_tmp.push_back(nums[middle]);
                    res_tmp.push_back(nums[right]);
                    res.push_back(res_tmp);

                    while (middle + 1 < right && nums[middle] == nums[middle + 1])
                    {
                        middle++;
                    }
                    middle++;

                    while (middle < right - 1 && nums[right] == nums[right - 1])
                    {
                        right--;
                    }
                    right--;

                    if (nums[middle] == res_tmp[1] || nums[right] == res_tmp[2])
                    {
                        break;
                    }
                }
                else if (nums[left] + nums[middle] + nums[right] > 0)
                {
                    right--;
                }
                else
                {
                    middle++;
                }
            }

            while (left + 1 < nums.size() - 2 && nums[left] == nums[left + 1])
            {
                left++;
            }
            left++;
        }
        return res;
    }
};

int main()
{
    vector<int> vec;

    // vec.push_back(-1);
    // vec.push_back(0);
    // vec.push_back(1);
    // vec.push_back(2);
    // vec.push_back(-1);
    // vec.push_back(-4);

    // vec.push_back(0);
    // vec.push_back(0);
    // vec.push_back(0);
    // vec.push_back(0);

    vec.push_back(-2);
    vec.push_back(0);
    vec.push_back(1);
    vec.push_back(1);
    vec.push_back(2);
    Solution so;
    for (vector<int> tmp : so.threeSum(vec))
    {
        for (int x : tmp)
        {
            cout << x << " ";
        }
        cout << endl;
    }
    return 0;
}

Python

# 15. 三数之和
# https://leetcode-cn.com/problems/3sum/

from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        #  a + b + c = 0

        nums.sort()

        ans: List[List[int]] = []
        ai = 0
        while ai < len(nums):
            a = nums[ai]
            if a > 0:
                break

            bi = ai + 1
            ci = len(nums) - 1

            while bi < ci:

                b = nums[bi]
                c = nums[ci]

                d = a + b + c
                if d == 0:
                    ans.append([a, b, c])
                    while ci - 1 > bi and nums[ci] == nums[ci - 1]:
                        ci -= 1
                    ci -= 1
                    while bi + 1 < ci and nums[bi] == nums[bi + 1]:
                        bi += 1
                    bi += 1
                elif d > 0:
                    while ci - 1 > bi and nums[ci] == nums[ci - 1]:
                        ci -= 1
                    ci -= 1
                elif d < 0:
                    while bi + 1 < ci and nums[bi] == nums[bi + 1]:
                        bi += 1
                    bi += 1

            while ai + 1 < len(nums) and nums[ai] == nums[ai + 1]:
                ai += 1
            ai += 1

        return ans


if __name__ == "__main__":
    pass